In today's society, individuals and businesses conduct an ever-increasing amount of activities on and over computer systems. These computer systems, including proprietary and non-proprietary computer networks, are often storing, archiving, and transmitting all types of sensitive information. Thus, an ever-increasing need exists for ensuring data stored and transmitted over these systems cannot be read or otherwise compromised.
One common solution for securing computer systems is to provide login and password functionality. However, password management has proven to be quite costly with a large percentage of help desk calls relating to password issues. Moreover, passwords provide little security in that they are generally stored in a file susceptible to inappropriate access, through, for example, brute-force attacks.
Another solution for securing computer systems is to provide cryptographic infrastructures. Cryptography, in general, refers to protecting data by transforming, or encrypting, it into an unreadable format. Only those who possess the key(s) to the encryption can decrypt the data into a useable format. Cryptography is used to identify users, e.g., authentication, to allow access privileges, e.g., authorization, to create digital certificates and signatures, and the like. One popular cryptography system is a public key system that uses two keys, a public key known to everyone and a private key known only to the individual or business owner thereof. Generally, the data encrypted with one key is decrypted with the other and neither key is recreatable from the other.
Unfortunately, even the foregoing typical public-key cryptographic systems are still highly reliant on the user for security. For example, cryptographic systems issue the private key to the user, for example, through the user's browser. Unsophisticated users then generally store the private key on a hard drive accessible to others through an open computer system, such as, for example, the Internet. On the other hand, users may choose poor names for files containing their private key, such as, for example, “key.” The result of the foregoing and other acts is to allow the key or keys to be susceptible to compromise.
In addition to the foregoing compromises, a user may save his or her private key on a computer system configured with an archiving or backup system, potentially resulting in copies of the private key traveling through multiple computer storage devices or other systems. This security breach is often referred to as “key migration.” Similar to key migration, many applications provide access to a user's private key through, at most, simple login and password access. As mentioned in the foregoing, login and password access often does not provide adequate security.
One solution for increasing the security of the foregoing cryptographic systems is to include biometrics as part of the authentication or authorization. Biometrics generally include measurable physical characteristics, such as, for example, finger prints or speech that can be checked by an automated system, such as, for example, pattern matching or recognition of finger print patterns or speech patterns. In such systems, a user's biometric and/or keys may be stored on mobile computing devices, such as, for example, a smartcard, laptop, personal digital assistant, or mobile phone, thereby allowing the biometric or keys to be usable in a mobile environment.
The foregoing mobile biometric cryptographic system still suffers from a variety of drawbacks. For example, the mobile user may lose or break the smartcard or portable computing device, thereby having his or her access to potentially important data entirely cut-off. Alternatively, a malicious person may steal the mobile user's smartcard or portable computing device and use it to effectively steal the mobile user's digital credentials. On the other hand, the portable-computing device may be connected to an open system, such as the Internet, and, like passwords, the file where the biometric is stored may be susceptible to compromise through user inattentiveness to security or malicious intruders.
One way to secure data from unauthorized access or unauthorized use is to use a secret sharing scheme. A secret sharing scheme is a method to split a sensitive piece of data (e.g., confidential files, an encryption key, or any type of communication), sometimes called the secret, into a collection of pieces, called shares, such that that possession of a sufficient number of shares enables recovery of the secret, but possession of an insufficient number of shares provides little or no information about the secret that was shared. Such schemes are important tools in cryptography and information security.
Formally, a secret sharing scheme consists of a pair of algorithms, the sharing algorithm Share and the recovery algorithm Recover. The sharing algorithm is typically probabilistic (meaning that it makes randomized choices), and the recovery algorithm is typically deterministic. The sharing algorithm may be used to disassemble, or split, the secret into a collection of shares, and the recovery algorithm may be used to reassemble those shares. At reassembly time, each share may be present, in which case a string may be provided to the recovery algorithm, or a share may be missing, in which case a designated value (referred to as “⋄” herein) may be provided to the recovery algorithm. A set of players that is authorized to recover the secret is called an authorized set, and the set of all such players is sometimes called an access structure.
Secret sharing schemes have been designed to work on various access structures, but the most common access structure is a threshold access structure, where any subset of m or more players, out of a total of n players in all, are said to be authorized. A secret sharing scheme for a threshold access structure is sometimes called a threshold scheme. There are two security properties for any secret sharing scheme: a privacy property and a recoverability property. The privacy property ensures that unauthorized coalitions of players do not learn anything useful about the secret. The recoverability property ensures that authorized coalitions of players can ultimately recover the underlying secret.
Shamir's secret sharing scheme is said to be a perfect secret sharing (PSS) scheme. The term “perfect” refers to the privacy guarantee being information theoretic and without any error; thus, unauthorized coalitions of players may learn nothing useful about the underlying secret in PSS schemes.
One limitation with PSS schemes is that the size of each share must be at least as long as the size of the secret that is being shared. When the secret includes a large file or long string of characters, however, this limitation can become unwieldy, increasing overall complexity of the system. In response to this limitation, schemes for computational secret sharing (CSS) have been developed.
Krawczyk's CSS scheme, for example, permits the shares to be shorter than the secret. For example, in a 2-out-of-3 threshold scheme (meaning that any two of three shares are adequate for recovering the secret), the secret S can be divided into shares of size about |S|/2 bits, where |S| denotes the length of S. Shares this short are not possible in the PSS setting. In CSS schemes, however, the privacy property may no longer be absolute and information theoretic; rather, an unauthorized coalition of players may obtain a small amount of information about the shared secret from their shares. But, under a computational complexity assumption, the amount of information will be negligible and therefore, in practice, not much of a concern.
A second limitation of PSS schemes concerns the lack of mandated robustness. Robustness means that a faulty or adversarial participant is unable to force the recovery of an incorrect secret. The model for PSS assumes that each share is either “correct” or “missing”, but it may never be wrong (e.g., corrupt or intentional altered). In practice, this is a highly unreasonable assumption because shares may be wrong due to any number of factors, including, for example, errors in storage, noise in a communications channel, or due to genuinely adversarial activities. In addition, the lack of robustness is not just a theoretical possibility, but a genuine problem for typical PSS schemes, including Shamir's secret sharing scheme. With Shamir's scheme, an adversary can in fact force the recovery of any desired secret by appropriately changing just one share. Practical applications of secret sharing schemes typically require robustness.